﻿//https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
//我的
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        for (int left = 0, right = nums.size() - 1; left <= right;) {
            int mid = (right + left) / 2;

            if (nums[mid] < target) {
                left = mid + 1;
            }
            else if (nums[mid] > target) {
                right = mid - 1;
            }
            else {
                //找到target
                int flag = 1;
                int begin = mid, end = mid;
                while (flag) {
                    flag = 0;
                    if (begin - 1 >= 0 && nums[begin - 1] == target) {
                        begin--;
                        flag = 1;
                    }
                    if (end + 1 < nums.size() && nums[end + 1] == target) {
                        end++;
                        flag = 1;
                    }
                }
                return { begin,end };
            }
        }
        return { -1, -1 };
    }

class Solution
{
public:
	vector<int> searchRange(vector<int>& nums, int target)
	{
		// 处理边界情况
		if (nums.size() == 0) return { -1, -1 };
		int begin = 0;
		// 1. ⼆分左端点
		int left = 0, right = nums.size() - 1;
		while (left < right)
		{
			int mid = left + (right - left) / 2;
			if (nums[mid] < target) left = mid + 1;
			else right = mid;
		}
		// 判断是否有结果
		if (nums[left] != target) return { -1, -1 };
		else begin = left; // 标记⼀下左端点
		// 2. ⼆分右端点
		left = 0, right = nums.size() - 1;
		while (left < right)
		{
			int mid = left + (right - left + 1) / 2;
			if (nums[mid] <= target) left = mid;
			else right = mid - 1;
		}
		return { begin, right };
	}
};